![](\"http://norvig.com/gesture.png\")
\n",
"\n",
"We'd like to know, for a given keyboard, how confusing is it? How many words have paths on the keyboard that can be confused for other words? We have our work cut out for us:\n",
"\n",
"1. Determine what letters could be confused for each other.\n",
"2. Determine what words/paths can be confused.\n",
"3. Invent some metric for the overall confusingness of a keyboard. \n",
"4. Try to find less-confusing keyboards.\n",
"\n",
"Letter Confusions\n",
"---\n",
"\n",
"So, as a first step, we will make a mapping from each key to the keys that it can be confused with. I'll say that any key within a distance of 1.5 units on the keyboard is a **neighboring** key, and thus a potential confusion:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def neighboring_keys(kbd, radius=1.5):\n",
" \"Build a dict of {Letter:NeighboringLetters}, e.g. {'Q':'QAW', ...}.\"\n",
" def neighboring_letters(A): \n",
" return cat(B for B in kbd if distance(kbd[A], kbd[B]) <= radius)\n",
" return {A: neighboring_letters(A) for A in kbd}\n",
"\n",
"def neighboring_keys(kbd, radius=1.5):\n",
" \"Build a dict of {Letter:NeighboringLetters}, e.g. {'Q':'QAW', ...}.\"\n",
" def neighboring_letters(A): \n",
" return \n",
" return {A: cat(B for B in kbd if distance(kbd[A], kbd[B]) <= radius)\n",
" for A in kbd}\n",
"\n",
"cat = ''.join ## Function to join letters (or strings) into one string"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 46
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"qwerty_neighbors = neighboring_keys(qwerty) \n",
"qwerty_neighbors"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 47,
"text": [
"{'A': 'AQSWZ',\n",
" 'B': 'BGHJNV',\n",
" 'C': 'CDGFVX',\n",
" 'D': 'CEDFSRXZ',\n",
" 'E': 'EDSRW',\n",
" 'F': 'CDGFRTVX',\n",
" 'G': 'CBGFHTVY',\n",
" 'H': 'BGHJNUVY',\n",
" 'I': 'IKJOU',\n",
" 'J': 'BIHKJMNU',\n",
" 'K': 'IKJMLON',\n",
" 'L': 'KMLOP',\n",
" 'M': 'KJMLN',\n",
" 'N': 'BHKJMN',\n",
" 'O': 'IKLOP',\n",
" 'P': 'LOP',\n",
" 'Q': 'AQW',\n",
" 'R': 'EDFRT',\n",
" 'S': 'AEDSWXZ',\n",
" 'T': 'GFRTY',\n",
" 'U': 'IHJUY',\n",
" 'V': 'CBGFHV',\n",
" 'W': 'AEQSW',\n",
" 'X': 'CDFSXZ',\n",
" 'Y': 'GHUTY',\n",
" 'Z': 'ADSXZ'}"
]
}
],
"prompt_number": 47
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see, for example, that **Q**, off in the corner, has only **A**, **W**, and itself as neighbors, while **G**, in the middle of the keyboard, has 8 neighbors. \n",
"\n",
"Word Confusions\n",
"---\n",
"\n",
"Consider each of the letters in the word \"HELLO,\" and all the possible choices for neighbors of each letter:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"choices = [qwerty_neighbors[L] for L in 'HELLO']\n",
"choices"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 48,
"text": [
"['BGHJNUVY', 'EDSRW', 'KMLOP', 'KMLOP', 'IKLOP']"
]
}
],
"prompt_number": 48
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Think of this as five \"columns\" of letters, and if we pick one letter from each column, we get a path that is formed by letters that are each confusions of letters in the original word, and so the whole path is a confusion for the original word. So \"JELLO\" is a confusion for \"HELLO\", as would be \"BEKKI\" (formed by taking the first possible neighbor for each of the five letters) and \"YWPPP\" (formed by taking the last possible neighbors), except they are not words.\n",
"\n",
"It turns out that there is a library function, `itertools.product`, that will take an iterable of alternative choices, and generate all possible ways of assembling a sequence consisting of one selection (letter) from each alternative choice."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"paths = {cat(letters) for letters in itertools.product(*choices)}"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 49
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"How many paths are there?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(paths)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 50,
"text": [
"5000"
]
}
],
"prompt_number": 50
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's look at a few of them:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"random.sample(paths, 8)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 51,
"text": [
"['JSMML', 'JRPML', 'VWMPP', 'JSPML', 'JDLML', 'VWPPK', 'GRLLK', 'BWOMK']"
]
}
],
"prompt_number": 51
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And let's see all the paths that are also words:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"WORDS & paths"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 52,
"text": [
"{'BROMO', 'BROOK', 'HELLO', 'JELLO'}"
]
}
],
"prompt_number": 52
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Only 4 out of 5000! That's pretty good, but it means \"HELLO\" is still a confusing word. We can wrap this up as the function `confusions`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def confusions(word, neighbors=neighboring_keys(qwerty), words=WORDS):\n",
" \"All valid words whose paths could be confused with the path for the given word.\"\n",
" choices = [neighbors[L] for L in word]\n",
" return {cat(letters) for letters in itertools.product(*choices)} & words"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 53
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"confusions('HELLO')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 54,
"text": [
"{'BROMO', 'BROOK', 'HELLO', 'JELLO'}"
]
}
],
"prompt_number": 54
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"confusions('WORLD')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 55,
"text": [
"{'ALTOS', 'EIDOS', 'SIDLE', 'SKEPS', 'WIELD', 'WORKS', 'WORLD', 'WORMS'}"
]
}
],
"prompt_number": 55
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"confusions('TESTING')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 56,
"text": [
"{'FEARING',\n",
" 'FRAYING',\n",
" 'GEARING',\n",
" 'GRATING',\n",
" 'GRAYING',\n",
" 'GREYING',\n",
" 'REARING',\n",
" 'REEFING',\n",
" 'RESTING',\n",
" 'TEARING',\n",
" 'TESTING'}"
]
}
],
"prompt_number": 56
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So far, so good. But I'm worried about the efficiency of `confusions` for longer words. \n",
"\n",
"More Efficient `confusions`\n",
"---\n",
"\n",
"Consider:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%time confusions('SOMETHING')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"CPU times: user 3.71 s, sys: 623 ms, total: 4.33 s\n",
"Wall time: 4.2 s\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 57,
"text": [
"{'SOMETHING'}"
]
}
],
"prompt_number": 57
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It took (on my computer) 4 seconds to compute this. Why so long? Let's count:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"[len(neighboring_keys(qwerty)[L]) for L in 'SOMETHING']"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 58,
"text": [
"[7, 5, 5, 5, 5, 8, 5, 6, 8]"
]
}
],
"prompt_number": 58
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are 7 × 5 × 5 × 5 × 5 × 8 × 5 × 6 × 8 = 8,400,000 paths for `confusions` to consider. Looking at them all takes 4 seconds, but for most of these paths, we're wasting our time. For example, one choice for the first two neighboring letters of 'SOMETHING' is 'XP', but 'XP' does not start any word in the dictionary. Nevertheless, `itertools.product` will generate 240,000 combinations that start with 'XP', and will then rule them out one at a time. It would be better to stop as soon as we see 'XP', and never consider continuations of this path.\n",
"\n",
"So that gives us the key idea for a more efficient version of `confusions`: *only follow paths that form a prefix of at least one word.* \n",
"\n",
"So, first we need to define the set of prefixes:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def prefixes(words):\n",
" \"Return a set of prefixes (1 to N characters) of this collection of words.\"\n",
" return {word[:i] for word in words for i in range(1, len(word)+1)}"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 59
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"prefixes(['THESE', 'THEY', 'THOSE'])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 60,
"text": [
"{'T', 'TH', 'THE', 'THES', 'THESE', 'THEY', 'THO', 'THOS', 'THOSE'}"
]
}
],
"prompt_number": 60
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's generate the prefixes of all the words, and check how many there are:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"PREFIXES = prefixes(WORDS)\n",
"\n",
"len(PREFIXES), len(WORDS)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 61,
"text": [
"(395184, 178691)"
]
}
],
"prompt_number": 61
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can describe the more efficient version of the `confusions` algorithm:\n",
"\n",
"1. Maintain a queue of partial paths, where a partial path is a string representing choices for neighboring letters for a prefix of the word. For example, 'HE' and 'JE' are both partial paths for the word 'HELLO'. Initialize the queue to have just one partial path, the empty string.\n",
"2. Remove a partial path from the queue. Find all possible ways to extend the path by adding a neighboring letter, but only if doing so creates a path that is a prefix of some word in the dictionary. For example, given the word 'HELLO', and the partial path 'JE', consider all the neighbors of 'L' (namely, 'K', 'M', 'L', 'O', or 'P'), but only 'JEM', 'JEL', and 'JEO' are prefixes of words, so add just those to the queue.\n",
"3. When a partial path reaches the same length as the word ('HELLO' in this example), then don't extend it any farther; instead check to see if the path is a word. If it is, add it to the set of paths/words that form the result."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def confusions(word, neighbors=neighboring_keys(qwerty), words=WORDS, prefixes=PREFIXES):\n",
" \"All valid words whose paths could be confused with the path for this word.\"\n",
" results = set() # A set of words that are confusions of 'word'\n",
" Q = [''] # A queue of partial paths \n",
" while Q:\n",
" path = Q.pop()\n",
" if len(path) < len(word):\n",
" for L in neighbors[word[len(path)]]:\n",
" if path + L in prefixes:\n",
" Q.append(path + L)\n",
" elif path in words:\n",
" results.add(path)\n",
" return results"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 62
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's do one quick check to see if we are getting the same answers as before:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"confusions('HELLO')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 63,
"text": [
"{'BROMO', 'BROOK', 'HELLO', 'JELLO'}"
]
}
],
"prompt_number": 63
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And let's see how much faster this version is:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%time confusions('SOMETHING')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"CPU times: user 543 \u00b5s, sys: 155 \u00b5s, total: 698 \u00b5s\n",
"Wall time: 586 \u00b5s\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 64,
"text": [
"{'SOMETHING'}"
]
}
],
"prompt_number": 64
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We went from about 4 seconds to under a millisecond: that's more than 4000 times faster! We can do a bigger test:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def words(text): \n",
" \"Extract a list of all words from a text. Make everything uppercase.\"\n",
" return re.findall('[A-Z]+', text.upper())\n",
"\n",
"test_words = words(\"\"\"Hello world! Testing something: confusion paths on \n",
"multiple distinct inputs of various lengths. See if everything works \n",
"perfect, or poorly, or somewhere between the extremes.\"\"\")\n",
"\n",
"def test_confusions(words=test_words):\n",
" \"Run through some test words, printing and summarizing the confusions.\"\n",
" total = 0\n",
" for word in sorted(set(words)):\n",
" others = sorted(set(confusions(word)) - {word})\n",
" total += len(others)\n",
" print('{}({}): {}'.format(word, len(others), ' '.join(others)))\n",
" print 'Total of {} confusions for {} words'.format(total, len(words))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 65
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%time test_confusions()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"BETWEEN(2): BERSEEM BERSERK\n",
"CONFUSION(2): CONCISION CONTUSION\n",
"DISTINCT(0): \n",
"EVERYTHING(0): \n",
"EXTREMES(3): ESTEEMED EXTERNES SCREENED\n",
"HELLO(3): BROMO BROOK JELLO\n",
"IF(7): ID IT OD OF OR OX UT\n",
"INPUTS(6): IMPURE IMPUTE KNOUTS OBLIGE UMPIRE UNPURE\n",
"LENGTHS(0): \n",
"MULTIPLE(0): \n",
"OF(6): ID IF IT OD OR OX\n",
"ON(3): IN OH OM\n",
"OR(7): ID IF IT OD OE OF PE\n",
"PATHS(7): LARGE LARVA LATHE LATHS OATHS PARGE PARVE\n",
"PERFECT(2): PREFECT PRETEXT\n",
"POORLY(1): LIKELY\n",
"SEE(20): ADD ADS ARE ARS ASS AWE DEE DEW EDS ERE ERR ERS ESS EWE SER SEW WED WEE ZED ZEE\n",
"SOMETHING(0): \n",
"SOMEWHERE(1): WINDSURFS\n",
"TESTING(10): FEARING FRAYING GEARING GRATING GRAYING GREYING REARING REEFING RESTING TEARING\n",
"THE(5): FUD FUR RUE RYE TYE\n",
"VARIOUS(3): CARIOUS CAROLUS FATUOUS\n",
"WORKS(13): AIRNS AKELA AKENE ALTOS EIDOS SIDLE SKENE SORNS SPEND WIDOW WIELD WORLD WORMS\n",
"WORLD(7): ALTOS EIDOS SIDLE SKEPS WIELD WORKS WORMS\n",
"Total of 108 confusions for 25 words\n",
"CPU times: user 7.21 ms, sys: 2.06 ms, total: 9.27 ms\n",
"Wall time: 7.84 ms\n"
]
}
],
"prompt_number": 66
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So, 108 confusions for 25 test words, or an average of 4 confusions per word.\n",
"\n",
"Visualizing Paths on a Keyboard\n",
"----\n",
"\n",
"To determine if these `confusions` are good ones, let's build something to visualize paths on a keyboard. \n",
"\n",
"\n",
"I'll add functionality to `plot_kbd` to call the new function `plot_paths` and implement that:\n",
"\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def plot_kbd(kbd, K=20, words=()):\n",
" \"Plot the keyboard with square keys, K units on a side.\"\n",
" H = K / 2 ## (K is Key width/height; H is half K)\n",
" # Draw a square for each key, and plot paths for words\n",
" for L in kbd:\n",
" x, y = K * kbd[L].x, -K * kbd[L].y\n",
" plot_square(x, y, H, label=L)\n",
" plot_paths(kbd, K, words)\n",
" # Show the plot and print the workload average\n",
" plt.axis('equal'); plt.axis('off'); plt.show()\n",
" \n",
"def plot_paths(kbd, K, words):\n",
" \"Plot paths for each word.\"\n",
" for (i, word) in enumerate(words):\n",
" Xs = [+K * kbd[L].x for L in word]\n",
" Ys = [-K * kbd[L].y for L in word]\n",
" plt.plot(Xs, Ys, '-o')"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 67
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see how it works:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"plot_kbd(qwerty, words=['HELLO', 'JELLO'])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "display_data",
"png": "iVBORw0KGgoAAAANSUhEUgAAAYMAAAD7CAYAAACIYvgKAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGZ9JREFUeJzt3XtcVHX+x/H3wICCgItIpaK/wPtPUHFNU7w8st0HeSm3\nsjVtu9jWJqb98tbPXWtjtdVda72Utbba1m/VxbSyNhE1TTeNQS1nSxEwTfJCJdcSEFSY3x8GCaLO\nwDnDDL6ej8c89sGk5z1n58y8+ZzvnNHicDgcAgBc03wa+wEAABofZQAAoAwAAJQBAECUAQBAlAEA\nQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBA\nlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECU\nAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQB\nAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEA\nQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBAlAEAQJQBAECUAQBA\nkrWxH8C1olWrViosLHRLlsVikcPhIMsLspriPjXVLHfuU2hoqAoKCtySVcXicNfeXeOa4ouDLO/J\nIct7ctydVYXTRAAAygAAQBkAAEQZAABEGQAARBkAAEQZAABEGXikvLw83XvvverUqZM6d+6sp59+\nWhUVFYbnTJ06VUuWLKn+OT4+Xo8++mj1z9OnT9eiRYsMyfL19VVsbGz1bcGCBYZs90pZffr00bRp\n03T27FnTsvLz86v3qU2bNoqIiKjOPnfunGE5DodDgwcP1qZNm6rvW7dunYYPH25YRpXs7GzFxMTU\nuC8xMVF/+ctfDM8KCgoyfJtX4q7XVtUx+NOf/lQzZ8409FgwC2XggR566CF17txZdrtdmzdv1oED\nB2q8aRtl0KBBSk1NlSRVVlYqPz9fBw8erP7vNptNcXFxhmQFBgZq9D336njFdzrqKNSCVcuUOO/P\nhmy7riy73a49e/boyJEj2rJliyk5khQWFia73S673a6JEydq2rRpstvt2rdvn/z8/AzLsVgsWrZs\nmaZNm6by8nIVFxdr9uzZeuWVVwzLuFq+N233cgYOGqx/fbhZuQFnledbprfeWW/Ka6vqGExLS9PB\ngwe1efNmwzOMRhl4mNOnTys9PV1z585VcHCwoqKiNH/+fL3zzjuGZw0YMEA2m02SlJ6erujoaAUH\nB6uoqEjl5eXKyMhQnz59DMk6e/as/rj2T8q/+6i+u/Mr5d99VH9c+yfTCkGSrFarhg4dqu3bt5uW\nUZuZV4326NFDt99+u/785z9rzpw5evDBBxUZGWlaXlPz22fn6Iujh3Tm8SJ9P+a4isad0OHK41r8\n4oumZfr5+WnYsGHatWuXaRlGoQw8zMaNGzV48OAa93Xv3l0nTpzQqVOnDM1q27atrFarjh8/LpvN\npgEDBqhfv36y2Wz65JNPFBMTI6vVmK+vOnv2rM5/WyQt04VbunT+ziItffNvhmy/Lt99951SUlLU\nu3dv0zLc7dlnn9Xq1au1efNmPfXUU439cLzK0teXSt0qa9xXMe60TuacNPy1VaWoqEgbNmxQfHy8\nKds3El9U54HqGp0dDodKSkoMzxo4cKBSU1OVmpqqadOm6eTJk0pNTVXLli01aNAg44J8LNLES39r\nLmj2rUbOe16923fVkO7dNDg6UoHNG3Z65cyZM4qNjdXhw4cVFxen+++/v0Hb8ySBgYG69957FRwc\nbOhpqIvV9b04DofD7ad0jFZhcUh17ILD4jB8oqs6BkNCQjR69GgNHTrU0O2bgTLwMCNGjNCsWbNq\n3JeRkaHy8nJTTgnExcXp448/1v79+xUTE6P27dvrhRdeUMuWLfXwww8bnleb47xFG79+TRvPZWne\nl5L+ZZV/SUe1quymDi26qsf13dS/Y1cN69nV6W0GBATIbrfr+++/17Bhw7RhwwaNGjXKvJ1wMx8f\nH1PfmCMiIlRUVKRz585VF87BgweVkJBgWqY7BAS10Jmv8mremSv5Wq26/vrrjc364Rj0Jpwm8jDB\nwcHq0aOHEhMTdfr0aX355ZeaPXu2Jk2aZErewIEDtWHDBoWFhclisSg0NFRFRUWy2WwaOHCgYTn+\nVj9Z1/+kxn3W9T/Rs2OeVvaMTL1wXZ76H06W3+5ZOl8YoVMttmmP3wK9XvCwJu6NU5fXWkszwxTy\n5CB1nfmIRs57XrNX/kubPzmk0rK6P6kREhKi5cuX66mnnnL7N0B6M19fX91yyy1KSkqSJB06dEif\nf/65V/x2eyVT7kuQpcIqbZdULqlAsqz00y1Db23sh+YRmAw80BtvvKHJkyerd+/eOn78uB555BH9\n/ve/NyUrOjpa+fn5+tWvflV9X8+ePVVaWqpWrVoZllNRUaHwUwHK/VOpHHKoWXALPfXkLCX+7n8l\nSdMTwjQ9YYTKy0do1y4pOaVC732YrlP+abrupzadCbPp6xZZKmmRpq99Dim3LFQff/4TLfgsT+cD\nTsq/9MbqaaL83Hm9ujFVw3p2VWxsrDp16qS1a9dq7Nixhu3P5bjrVIrZOXPmzNGSJUu0aNEiRUVF\n6eWXX5aPj/G/O7rz1FPi7/5XpSUlWvLyQp2zlcnhU6Eu/91Lmza8b3iWN55S498zcJP6fj+5zWbT\no48+qnXr1ql79+6mZtWH2VlffSVt2iRt3Cj964Oj6jIsQ9f3telMa5sOFe/VDUE3qGd4rPzOhevc\n96EqyLcq+7vD+rYiSyUBmbJU+iuorKva+HVTp9CuTq9N8B35TT9r9J8W6tNTqTqx8C1Tc+qjMf49\nA8rATZrqgeTerGbaurVcKSlSSor0bW6F+o9K1w1901QaZpM916ac0zm6qd1NGhAxQDe3G6Dgihtl\nP5SrvUezlJmbpeNnMlXom3XJNHHx2kTniDDK4BrIyvuuVNf/saPevH2zxgzuaVpOfVAGTVhTPZAa\nM+viqWHHDqlbN2no8Hy16btbeQE27T5p056Te9QmuM2Fcoi4WQMiBij6umidLj2n7Z8dVmpWlv5z\nMlNffpdVY5pw5LZRl1b9XJomjNgnM5F1KVemA2/Zp3pnUgbu0VQPJE/JKi+Xdu1S9dRw6pQUHy/F\n31ahDn3TlVlsk+2ETWkn0mpMD1UlERYYJkmqrHToQPa36nXrbRr/RIJL04TR+2Q0si7lynTgLftU\n70zKwD2a6oHkqVlVU0NKirR9+4WpYfjwC7fI/87XJ9/slu34hYKoa3ro3ba3HJU1s4qKyy6dJs5n\nqSTQ89cmyLo8Z6cDb9qnemVSBu7RVA8kb8i63NQwfPiF/w1tVaH03PTqckg7kaasnCwN6zaszumh\ntqpp4sPPMz12bULyjueqMbKcnQ68aZ/qlUkZuEdTPZC8MetKU0PfvpKvr2QJtCj5s+QrTg/R10XL\n18f3ill1ThMVmSoJyHLr2oTknc+Vu7KcmQ68bZ9czqQM3KOpHkjennW5qWH16vuUm7tarVtf+HMV\nlZdOD1dae7gad69NSN7/XJmZ5cx04G375HImZeAeTfVAampZVVPDxInvKiTkF3VODVXyS/O1++SV\n1x6uNj3UtU9XmybqszZxuSyzeGPW1aYDb9wnlzIpA/doqgdSU84qK3Ncca2hamqoUp/pwZV9qr02\nkXEqSyfKnJ8mmvJzZUTW1aYDb9wnlzIpA/fwxsvTUVsHSbdJGi7pFkmZklJ+uH0iqfLSvxIgKeKH\nW3tJ7SSdlnTih9txSackNfRVaPWXWrW/0FBhzaXW56TWRVLYCanCT8pvK+W1lPJ8pPwzUt4pqfCE\nVGn8v/Ll1QYMkdqXS2t3N+rDCA0NVUFBgVszKQMP1xR/G2kK+1TXWkNe3iqtWvWrOqeGKkatPTi7\nX5dOE5k6UZbl0trEtXRcuHpVckOyPA1l4OE84QXirTnuzPrqK+nGGx/T6NGvXvYTSpdTe+1hb86F\n71yqKocB7QeoR3iPGmsPRuxX1drErsxMfZ6Tddm1iUOpX+h3E6eb+kknyXOOC1e/s6ghWZ6EMvBw\nnvIC8cacxso6e/bHqWHjxquvNdRWe3qwnbDp69Nf15geRvUeJUepOftVe5r45+Z/Krx7C1M/6SR5\nznFh9HRAGcAQnvIC8cYcT8k6duzH00muTg1Vak8P2zK3qUvbLlecHszYL2enifpcN+EJz1UVI6cD\nygCG8KQXiLfleGJWQ6eG6iwfiz77+rMrTg+uXPfQ0P2qrHTo86PfaMf+rFprE5k6H5DjUWsTzmQZ\nOR1QBjCEJ71AvC3HG7LqOzXUlXWl6x4aMj009P9DT1ubkJzbJ6OmA8oAhvD0NzNPzvG2LFemBmey\nnFl7MPKTS66qPU38uDbh/DRRX87sk1HTAWUAQ3jTm5mn5Xh71pWmhptv9pXD4fo1AvWZHhrjuKg9\nTRwpytSpyixD1iZqZ12JEdMBZQBDuHogvfvuu7rrrruUkZGhrl27mpa1fPlyrVq1SoWFhfL19dWr\nr76qfv36GZrj6+urnj17qqSkRC1btlRCQoImTJjg0gV8rmZVee+999ShQwenc1zJkqTCwkLNnDlT\n27dvV7NmzRQSEqJZs2bpF7/4RZ1//uKpISVFSk/P1X33hV91rSEoKEjFxcXVP7/xxhv69NNP9dJL\nL0ky55NLtTOd5ezaRFBwkOatTtaeLzO1O22Tvtq6VRrTShXXn3J6mnD2uWoRFKSyScENmg4oAxjC\n1QNp7NixOnPmjPr06aPExERTsnJycnTbbbcpLS1NgYGBKigoUHl5udq0aWNoTnBwsE6fPq2Kigpt\n3bpViYmJGjt2rJ588kmncuqT1RCuPFdjxoxRly5dNGXKFLVp00aHDx/Wu+++qxkzZjiZ1UHLlh27\n6lpDcHCw1qxJ1osvblF5uVV5efsUGWnV+++/c9ltN+STS8kfJGv0iNEadN8gNbM00xPjn9DIn490\ncp9ce662bdumiRMnasuWLYqMjHRpmtj4j3XatGrVVaeJ4OBg+cdEqKAwS5JVOmvRkG4/07+Tk53a\nJ1f2q7FRBh7OlQOpuLhY0dHR+uijjxQfH6+MjAxTsnbs2KHnnntOW7dudWn7rubUfoNev369Hn/8\nceXk5JieVR/OZpWUlCg6OlpHjx41JKv21PDttz+uNTzySKDatZuqI0f++MPffEMhIUv1z38u1MiR\nQ5zLcvKTS2kfp+l/Xv4fHUk5Iv3uwt/taO+oJY8vcaoQXHmukpOTNWHCBKWkpKhLly5X/PMXr03s\n+TJTmblZsh/fJesN+Vddm7BararoWSmNvuhxvWfRkDbDnS4EygCGcOVAWr16tXbu3Klly5ZpyJAh\nWrx4sfr06WN4lsPh0K233qojR45o9OjReuKJJ9SpUyfDc2q/QRcXFys8PFy5ubkKCgoyNMtqtSom\nJkaSFBUVpbffftup7dcna+3atXr//fe1cuVKlzOcybp4reG993wk9brovxZIGq34+JbatGluvbPq\nWnuo2Fqh0iGl0jxVl4EkxX8Vr01/39SgfbqYn5+fQkJC9O9//1vR0dFO7cPlsq42TTiez5N+X8cG\nVvrLcbjcpSxPZ23sBwDjJCUlaerUqZKke+65R0lJSS6VgbMsFos+/PBD7d27V2+99Zbi4uL0+uuv\na8SIEYZnXczhcMjhcJjypX8BAQGy2+2Gb7cutR//5MmTtWvXLvn7+2vPnj0N3n6HDtJjj124Wa1+\nqqi4eL/+T9InKitr2MVpYYFhGtF5hEZ0vvCcV1RWqP/+/vpUn17yZ8sqyxqUVZu/v7/i4uK0YsUK\nLV68uEHb+klQc90ZF60742qWStU0Eft827r/op/nv7m7ijJoIgoKCrR9+3YdOHBAFotFFRUVslgs\nev75503LvOmmm3TTTTepe/fuSkpKMr0MtmzZotatW6tFixam5pht+PDhmjFjRnWxLV26VPn5+erb\nt68b0i+8iTVvbuy3lfr6+CqsWd0f+Wzu09zQLB8fH61du1bDhg3T/Pnz9dvf/tbQ7V/IsKh3xzaX\n/zbZc03vW4h9GvsBwBhvvfWWHnjgAWVnZ+vo0aM6duyYIiMjtXPnTsOzDh06pC+++EKSdP78eaWl\npWngwIGG51SpWkBeuHChZs6caVqOuwQFBalv376aPXt29fpHSUmJKVn+/r7q2HF2jftCQmyaMuXn\nhmc9Mf4JdbR3rHFfx30dNWXcFMOzmjdvruTkZK1evVp///vfDd9+FV8fX+m9Wm/871o0pOvPTMts\nLEwGTcSaNWs0a9asGvfdfffdWrNmjQYPHmxoVnFxsaZMmaKioiIFBQVpwIABevDBBw3NkKQzZ84o\nNjZWJSUlCgkJ0aRJkzRhwgTDcyT3/3sTK1as0IwZMxQXF6fw8HAFBQVpwYIFhudYrVYtWRKvl156\nRmVlvsrP36fIyP9yevHYFSN/PlLl5eW674P71P9ofzX3aa4pk6c4/WkiZ1U9V6Ghodq0aZOGDBmi\n6667TqNGjTI0R7pwatI/o5nOfl4mWSS19NWQ/vEufZrIW7CA7OG8+aKpxs4hy/1Z27dv19/+9jcl\nJSWZmtNQTTWrIZgMABjir3/9q95++20999xzjf1QUA9MBh6uKf4G0xT3iSzvyWnKWQ3BAjIAgDIA\nAFAGAABRBgAAUQYAAFEGAABRBgAAcdGZV3DnVyW4K6sp7hNZ3pPjzqzQ0FC35DQUZeDh3HmxChcX\nkdWYWU1xn7wJp4kAAJQBAIAyAACIMgAAiDIAAIgyAACIMgAAiDJAPaxfv16xsbE1br6+vtq8ebOh\nOcePH1dUVJQKCwslSYWFhYqKitKxY8cMzalSWFioCRMmKCoqSj169NDIkSP1xRdfGJ4zbNgwbdmy\npcZ9ixcv1qRJkwzP8vX1VWxsrHr16qWRI0fqwIEDhmdU8fHx0YwZM6p/fuGFF/SHP/zBlJz777+/\n+ufz588rPDxct99+u+FZ1xLKAC678847Zbfbq28JCQkaMmSI4uPjDc1p3769EhISNGvWLEnSrFmz\n9Nhjj6lDhw6G5lT59a9/rRtuuEG7d+9Wenq6nnnmGeXk5BieM27cOK1Zs6bGfW+++abGjx9veFZg\nYKDsdrs+++wzPfTQQ5o7d67hGVX8/f21fv165efnSzLvCt8WLVooPT1dZWVlkqQPPvhAERERbr16\nuSmiDNAghw4d0ty5c7Vy5UpTtj916lSlpaVp8eLFSk1NrfGbp5GKi4u1b98+zZ8/X+Hh4ZKkm2++\nWUOHDjU86+6771ZycrLOnz8vScrOzlZOTo4GDRpkeFYVh8OhvLw8NW/e3LQMPz8//eY3v9GiRYtM\ny6gyYsQIJScnS5KSkpI0btw4rihuIMoA9Xbu3DmNHz9eCxcuVEREhCkZVqtVCxYs0LRp07R48WL5\n+vqakrNx40YNHjzYlG3X1qpVK/Xr108bN26UJK1Zs0Zjx441JevMmTOKjY1VZGSkEhMTNW/ePFNy\nqkyaNEmrV6/W999/b2rO2LFjtWbNGpWXl2v//v3q37+/qXnXAsoA9fbMM88oJiZG99xzj6k5KSkp\natu2rfbv329ahrtPMVx8qujNN9/UuHHjTMkJCAiQ3W5Xdna2XnnlFY0ZM8aUnCrBwcF64IEH9OKL\nL5qaExMTo+zsbCUlJWnkyJGmZl0rKAPUy44dO7R+/XotXbrU1Jz//Oc/2rp1q2w2mxYtWqRvvvnG\nlJzhw4dr586dpmy7LnfccYe2bdsmu92u0tJSxcbGmp551113KSMjQ6WlpabmPPnkk3rttddUUlJi\nas4dd9yhGTNmcIrIIJQBXFb1qZt//OMfatGihWk5DodDCQkJWrJkidq3b6+ZM2eatmYQFBSkPn36\n6Omnn1Zubq4kae/evfroo49My7vllls0YcIEUxaO6/Lxxx+rc+fOCgwMNDUnNDRUv/zlL/Xaa6+Z\nOnE9/PDDSkxMVI8ePUzLuJZQBnDZsmXLlJubq4kTJ9b4eOm6desMzVm+fLluvPFG3XrrrZIunI/O\nyMgw7Tf4FStW6MSJE+rXr5+io6M1Z84ctWvXzpQs6cKpov3795t2ikj6cc2gV69eWrBggRYuXGha\n1sVv/NOnT1deXp6pOe3atdPkyZOr7+PTRA1jcTBf4Qd8bz1ZjZnVFPfJmzAZAAAoAwAAZQAAEGUA\nABBlAAAQZQAAEGUAABBlAACQZG3sBwDP4q6rON15tShZ3pPlrpzQ0FC35HgTygDVuCITuHZxmggA\nQBkAACgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAo\nAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgD\nAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMA\ngCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCA\nKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAo\nAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgDAIAoAwCAKAMAgCgD\nAIAoAwCAKAMAgCgDAIAoAwCApP8H0fl69wTQkGkAAAAASUVORK5CYII=\n",
"text": [
"**Answered**: \"PALEOMAGNETISMS\" etc.\n", " 2. What words have the highest ratio of path length to word length?
**Answered**: \"PALAPA\" etc.\n", " 3. What is the average segment length, over a typical typing work load?
**Answered**: 3.23 keys, for Qwerty keyboard, on our sample workload.\n", " 4. Is there a better keyboard layout to minimize the average segment length over a work load?
**Answered**: Yes, many layouts at around 1.9 on Qwerty; or 1.7 or 1.8 on more square keyboards.\n", " 5. How often are two words confused because they have similar paths?
**Answered**: On Qwerty, 26% of the words in a small dictionary, and 55% of the words in running text have at least one possible confusion. Other layouts are worse.\n", " 6. Is there a better keyboard layout to minimize confusion?
**Partially Answered**: We found a keyboard with less confusingness than Qwerty. The computation of confusingness takes too long to do very much hillclimbing search. \n", " 7. Is there a better keyboard layout to maximize overall user satisfaction?
**Partially Answered**: We defined a combined metric, and found\n", "a keyboard with a better score. There are no doubt better metrics, and better keyboards to be found.\n", " \n", "\n", "\n", "\n", "Going Beyond\n", "===\n", "\n", "Now it is your turn to answer the open questions, or make up some questions of your own. Good luck! Here are a few ideas to get you started:\n", "\n", "* Hillclimbing just keeps the one best keyboard it has found so far. Other optimization techniques such as\n", "[beam search](http://en.wikipedia.org/wiki/Beam_search) or [genetic algorithms](http://en.wikipedia.org/wiki/Genetic_algorithm) or [ant colony optimization](http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms) maintain several candidates at a time. Is that a good idea?\n", "\n", "* The code in this notebook emphasises clarity, not efficiency. Can you modify the code (or perhaps port it to another language) and make it twice as efficient? 10 times? 100 times?\n", "\n", "* What other factors do you think are important to user satisfaction with a keyboard. Can you measure them?\n", "\n", "* Consider the 5 paths below. They all start at 'P', move in a straight line to 'T', and then go to 'S', but they all make different stops along the top row. In other words, the 5 paths all trace exacty the same lines, so they are very confusing, but our definition of `confusions` makes most of them different. Can you think\n", "of a better way to handle confusions for paths like this?" ] }, { "cell_type": "code", "collapsed": false, "input": [ "plot_kbd(qwerty, words=['PUTS', 'POTS', 'PITS', 'POUTS', 'PUTTS'])" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "display_data", "png": "iVBORw0KGgoAAAANSUhEUgAAAYMAAAD7CAYAAACIYvgKAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHPZJREFUeJzt3XlYVPXix/HPAAooLpBomriRpletcEVwKbuJSmFZVtov\nb2ba1Qcwt3JNtKybaSpa3cqyW9fQtEftirnkUpa23KTrkmnqtUzr5oK5AQJ+f38YxDLDMswZBny/\nnsfnkcOc85nvzMBnvuecOdiMMUYAgKuaV3nfAQBA+aMMAACUAQCAMgAAiDIAAIgyAACIMgAAiDIA\nAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAA\niDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACI\nMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgy\nAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIA\nAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAEjyKe87cLUI\nCgpSamqqW7JsNpuMMWRVgKzKOKbKmuXOMQUGBur06dNuycphM+4a3VWuMv5wkFVxcsiqODnuzsrB\nbiIAAGUAAOCYAVAiyRuTlfhuojJMhnxtvoofFK/o26OLXe+T5GRtSEyUT0aGsnx91Ss+Xt2ji18P\nVzjz+Dn7XDmjMr0uKAOgGMkbkzXqpVE6FHYod9mhl678v6gf/E+Sk7V+1CjNPPTHepN//395/+BX\nBM48fs4+V86obK8LDiC7SWU9+HQ1ZEUNidKGJhsK3abWZ7XU8r6WDrdRc84+bfjubKHlj/t76dFr\n/SVJ589fUEBAdRfd66JVtKzXf07T/PTLhZbnffwKZqWdTld2QHahdbzPe8s/yK9M96fgmBxl1bpU\nS62aOX5dTNm3T8+cLfy6mBoVpafXrZNUPgeQmRkADmRmZ2r1/tX68ucvpSaFv9/smmaa13teoeX+\n3x1S3XdX65Xvv7K73SrNrpeeHS9JevzRYVo0r/A2rFDRsqpOekHae6DQ8ryPX8GshQte0P7Ghde5\n4YdQjY8bX2h5aRQck6Osdj8308tTHY/dZ+RIKSWl0HLv9PQy3b+yogyAAg6dPiTdJoXMDdENdW5Q\nSI0QndGZQrer619X4Q3Dr3xx8aK0fLn02mvSkSPS0KG6HBEpbdtWaD2/hk3VJuZRSdIXJ4bl/t9q\nFS3L96Xldssg7+NXMOuXlcv1RUjhdWpfblrm+1NwTI6z6krh4Q63kxUcbHd5tl/ZZi5lxdlEHujk\nyZN64IEHdP3116t58+aaMmWKsrMLT0fLavTo0Zo/f37u11FRURo2bFju12PHjtXcuXNdkuXt7a2w\nsLDcf7NmzXLJdovKateuncaMGaNLly4Vu05mdqZWfLtCvd7ppfA3wiVvaevDW/Xxwx/rueHPKTQl\nNN/tQ3eGKm5gnE59+qnCgoMVVrOm6j/2mBru36+w4GC1W7NGPceO1eTQ/OtNCg3V7XFxpR6TMUbd\nunXTut93I0jS8uXL1adPn1JvqzhHjhxR27Zt8y1LSEjQnDlzXJ4VEBDg8Hu94uNL/fjFD4p3+FxJ\nrv3ZKior5zXYvn17jR8/XpmZmWUal1sYuEVpHuro6GgzZcoUc/bsWXPo0CHTr18/M2fOHJdnrVix\nwtx3333GGGOys7NN+/btTURERO73u3TpYr744guXZAUEBJTodq7MyszMNDExMeZf//qXw9sePHXQ\nTNg4wdR7oZ7pvri7WbJriUnLTCuUtWbDGhM1JMr0+EsPE/PQn03KuNHGREQY06CBMVOnGnPkiElI\nSCj0PH28Zo2ZEhVlpvXoYaZERZmP16xxakzGGLNnzx7TqlUrk56ebs6dO2eaN29uDh8+XOL1S5r1\n3//+17Rp0ybfsoSEBDN79myXZxX3uiju8bOXlfe5ihoSZdZs+GOdsvxs2RuTo6yccV26dMn07du3\n0GvQla8LV6EM3KSkT+7Zs2dNkyZN8i379ttvTWRkpMuzjh07ZkJCQowxxuzatcv85S9/MVFRUSY1\nNdWkp6eb2rVrm8zMTJdklUcZGGPMnDlzzJgxY/J9/1LWJbN873Jz+9u3mzqz6pgx68aYfSf2FZ+1\ne7cxcXHGBAUZ07evMatWGZPn8SntL0yHOUV44oknzPTp08348ePNM888Y0mWJ5WBK7PK+rNVmucq\n77hmz55tnnzyyRKvW9osV+GYgYdZu3atunXrlm9Zq1at9NNPP+nXX39V3bp1XZbVoEED+fj46OjR\no9qxY4e6dOmiY8eOaceOHapZs6batm0rHx/XvETS0tIUFhaW+/WkSZM0YMAAl2zbkd9++00ffvih\nBg8eLOnKsYBFOxdp8TeLdUOdG/RY+8f0QasP5OdTxL7atDTpvffyHQvQzp1S48aW3ndHpk2bprCw\nMPn5+enf//53udyHisqdP1s5zpw5ozVr1uipp55y+bZdjTLwQDabrdAyY4wuXLjg8qyIiAht375d\n27dv15gxY3Ts2DFt375dtWrVUteuXV2W4+/vrxQ7Z1BYIad4Dh48qIiICPm391evd3op5ZcUDb5x\nsLY+vFUt6zg+9U+SWktSfLy0ZMmVg4FPPCFFR0suKkdnVatWTQ888IBq1KihKlWqWJJh77RGY4zd\n12VFY28MVpzGmfMarFmzpvr166cePXq4dPtWoAw8TN++fTVhwoR8y/bt26eMjAw1bdrU5XmRkZH6\n7LPPtHv3brVt21YhISGaPXu2atWqpUceecTlee7g7++vFZtW6KVtL2lB7AIde+2YJg2dVKpZwHpJ\nql27XGcBjnh5eVn6i7lhw4Y6c+aMMjMzcwvn22+/1YgRIyzLdAdHP1sNGjRQvXr1XJrlzjc/rsLZ\nRB6mRo0aat26tRISEnTu3DkdPnxYkydP1siRIy3Ji4iI0Jo1a3TNNdfIZrMpMDBQZ86c0Y4dOxQR\nEWFJplVyzghKy0pT+BvhsvnZtOwfy3R5w2UNbDPQcRHs2XNlFtCw4ZUyeOIJNZakGTM8rgjcwdvb\nW7feequSkpIkSQcOHNCuXbsqxLvbotj72Zo0aZL69+9f3nfNI1AGHuitt97Sd999p5tvvlktW7bU\ntddea9k+xzZt2ujUqVMKz3Ne9I033qjatWsrKCjIZTk50+acf5MmTXLZtg+nHtbEjyYqZG6IFny5\nQFW8q+jo6KOaEzVH/Xv21/XXX6/33nuv4B2S/vEPKTJSior6YxaQnCz16ydnT+R1164Uq3NmzJih\nnTt3KiwsTBMnTtRLL70kLy/X/7pw966nvD9bvXr1UqtWrTR69GiX51TEXWpcjsJNnN0vuWPHDg0b\nNkzLly9Xq1atLM1yRnllZWZn6oP9H+jVr1/NPRYwrP2wYo8FaM+eKweDc44FDB9u91hAwXGNHDRa\nO5d/JT/jp3RbutoN6KiX3y3+MxjJmzcrcdUqZdhs8jVG8XfdpeiePR3mWMle1vMJifpg4TpVyaqq\nTJ9LiontrScT4ovcTnFjcpRlFVdlOfNcOfP4OZtlNY4ZeLguXbpoz5495X03PMbh1MN6/evX3XpG\n0MhBo/VD0vf6m57JXfZC0myN1OgiCyF582aNSkrSoQcfzF12aMkSSSr0y7M8PJ+QqE0zt2pm1hO5\ny56dmShJDn+hefqYnOXMuJx5/JzNcgdmBm5SEd8peUpWzizg3r/dqzpt67h8FmBP3nGFV+mqv2U9\nU+g2k2xP6fHByxxuY+Pud3W8Z/tCy2tt/VKt298pSdq+fbvbjs0UzNq4bJoSzhQ+FjU98GX9+b7p\ndrex9+sP9NstnQstzzsme1lWckVWScZV0sdvXJP5GrH9ZYdZcxMStHfgwELLo1au1LrfrwjAzADI\no+AsQN9IR9886tbPBaSfvyz/LH+73/M3fjq7/Te738uomqU6F2orcG/h73mfCpLZc+Wqla0Vkvt/\nqxXMqpnpa/d2NS75OrxPjU9do+xixmQvy0quyCrJuEr6+Hl5+Wn7b/ZfF5J08nLhK7FKUvlepo4y\ngIexdywg53MBtiG2os8IyjsLKOPnAhqoi97sfEhBX/2iLGXavc0Fn4t69MAfs5OL2dl679df9erP\nP+toerp8F3+uww+GFlovauVurZt/5YJn5TmLi6wzXbLz0ZVTfqc15dPC75IlKSp+iTb0v77w8jxj\nspdlJVdklWRcJX38qvx2Vm+0dDxrjfL3V+ELokvle5k6ziaCh8h7RlDil4l6+OaHc88Icrg7qJgz\ngkpbBOnnL2v1mF+1OOgbLdTzMtlGzZPD1HZgmF7Q7Hy3naXZajegoyRp9/nzivv+e4Xs2KEVJ05o\nYqNGOhIersSBAxX6+77gHKH//Kfi+vUr1f2ySkxsbz3rk5hv2Uyf+YqJjXK4Tvxdd3n0mJzlzLic\nefyczXIHjhm4SUV7p+SOrNKeEZSbtXfvH7OAzp1LdSzAnu82XdT2ST8r6KtflFqrumr/X33dvzBU\nl8z53NsUPJvoxgEdFDHnydxZwND69TW0fn01KnAZ4uTNm7Vg9Wql68o7v7h+/TzwbKL1qpJVRZk+\nmYqJjSrR2URFjclRllVceTZRaZ8rZx4/Z7OsRhm4SUX84bAqy94ZQf1b9S/2WMDgatX0dkTEH8cC\nhg4t07GA9U+d1Om3jivozAWdbFdP4U83UOs+1Yoc1+7z5/Xazz/r3f/9T11q1tTwBg3UNyhIPk6e\ng+/pzxVZ7s9xd1YOjhnALYo6FlCkPLOA+6UyHwuwNwvoNTNY/jUd/zIveCxgaP36SunQodAsAKjI\nmBm4SWV9V1FclrOzAC1fLr36ar5ZgK1JE6fGVdwswNG4dp0759JZgKMcT3muyPKMHHdn5WZSBu5R\nET+e7jQvSTdI6iDpWkn/kbRT0smiV/uTpOGSHpT0haTXJCVLTl8aooG66A7FKkoh+kFZWqNN2qZ5\nyrR3CkgOX1/pllukO++U6taV1q698u/XX528F0DpBQYG6vTp027NpAw8XEV6N1LSWUC+HAezAFcd\nC1hnjip2bUyRswDJNccCKtJz5YlZlXFM7s4qC8rAw3n6i9aZawTZbDaZvJ8LsOiMoN4zg1WtlrfD\nMdk7FmDvjKCS8vTnytOzKuOY3J1VFhxAhlOcvkbQ8uX6VJJ69boyA/j6a5fNAky7emqeHFbqWcDE\nRo1cfiwAqGgoAziUvDFZie8mKsNkyNfmq5H3j1RWo6xizwj6JDlZGxIT5ZORoSxfX/Xq10/d9+/P\nnQXMkrT6hx84IwjwIOwm8nDlNZ1N3pisUS+N0qGwQ7nf99rspVbhrTTp/yY5PCPok+RkrR81SjMP\n/bHeZG9vRd17r7o//7zUuLFTY3LmjCBJsjVrptj16y09Iyg3q5LuemA3UcXJKgtmBrAr8d3EfEUg\nSZd7XlbDHxpqUNtBDtfbkJiYrwgkaWZ2tqaeOaPuTuwOKussQM8/ryAfH2YBQDEoA9iVYTLsLk+/\nXPS1FX0y7K/nnV7yazK68lhAv44dNT3b2ZNTgasHZQC7fG32L8/r51X0u+ssX/vrZZfgXbklxwIc\nXC4YQH6cPlHJrFq1Sl5eXtq/f3+ZthM/KF6hKfkvvxy6M1RxA+MkSa+//rp69OihG2+8UWFhYfry\nyy8lSb3i4zU5NP96k0JDdXtcnN2cvFcK3X97Su6VQoek3qx7X26giB7t1aJFC3Xs2FFvvvlm7r5X\nR1cKnd60qVO7g7y9vfP9jeYff/yx1NsojdTUVD366KMKDQ3Vn/70J4WHh2vVqlUuzwkICMj39Vtv\nvaU4B8+FVZlWbn/t2rW64YYbdPToUcuzKjtmBpVMUlKS7rjjDiUlJSkhIcHp7UTfHi1JWpC0QOmX\n0+Xn5ae42DhF3x6t48ePa8GCBfr8889VrVo1nT59Whm/7x7qHn1lvakLFsg7PV3Zfn7qHReXuzxH\nSWYB1apVU0pKirKzs/XRRx/pqWnT9NFPP+m/d9zh8jOCcrLcZdiwYWrRooU+/fRT1a9fXwcPHrSk\nDAp+8t0dn4S3OiNn+5s2bdKoUaO0YcMGhYSEWJp1VTDwaKV5is6dO2caN25sfvjhB9OyZUvLsrZs\n2WJuu+22Um8/7Vy2WTX6f2a2NplVtk/Novbfmz1rLzi8fUBAgDHGmF3nzpnYAwdMwMyZxjc42Kw+\nccJkZmeXKLOkY8rJKouSZp0/f940adLELVkFx7V48WITGxtrSZajTFfnBAQEmI8//tg0a9bM7N+/\n3/Kssqoov2bZTVSJrF69Wr1791ajRo0UHBysnTt3WpLTo0cPXb58WY0bN1Z8fLwOHjxY5O2/23RR\nb3Y+pHU1d+j04uNaq83qdaaLhv77eocHhS9mZyvLGHXZuVN9du1SkI+Pvhw+XLZz59TTz8/lp4am\npaXl7iK65557XLrtgpKTk9W1a1dLM3LkHVdYWJimTZtW4d/tpqen6+6779bq1avVokWL8r47lQZl\nUIkkJSVpwIABkqQBAwYoKSnJkhybzabNmzdrxYoV8vf3V2RkpNauXZvvNkUdC9ismQ4PCuc9FpBp\nTL5jAQ19fWWMseSXmb+/v1JSUpSSkqL333/f5dvPq+D9j42N1c0336xOnTq5PCvvuFJSUjRjxowK\ncc57UapWrarIyEgtWrSovO9KpcIxg0ri9OnT2rJli/bs2SObzabs7GzZbDa98MILlmV27NhRHTt2\nVKtWrZSUlKS+ffu69Iyg1l5eiqlTJ/d2GzZsUJ06dVS9enXLxuQOffr00bhx43KLbeHChTp16pQ6\ndOhgeXZFLwJJ8vLy0nvvvaeePXvqueee08SJE8v7LlUKlEElsWLFCg0ePFivvPJK7rJbbrlF27Zt\nU7du3VyadeDAAdlsNjVv3lxZWVn6bNsOVT/eVouDvrHkGkHZ2dnasmWLXnzxRY0fP96lYykPAQEB\n6tChgyZPnqzY2Fg1aNBAFy4UcVltFOLn56fk5GR169ZN9erV0yOPPFLed6nCowwqiaVLl2rChAn5\nlt1zzz1aunSpy8vg/PnziouL0/+OperyyapqfaGFomt1U+2HSjYLUFSUuuzcWewZQTn7uy9cuKCa\nNWtq5MiRGjJkiEvHksPd+9EXLVqkcePGKTIyUsHBwQoICNCsWbNcnmPvbCIrx5qWlqbatWtbtn3p\njzEFBgZq3bp16t69u+rWras77rjD5VkXL17Md6bS2LFj9fjjj7s8xxNwbSIPV57XULnyx77XqUpW\nVWX6XFJMbG+NGhdb7DWCkjdvVuKqVcqw2eRrjOLvukuNOnXKnQWc3rZNq4cNc8uVQivrNWg8NWvL\nli167bXXnDpe5aljqkhZZUEZeLjyetE+n5CoTTO3alJWfO735+sVdVSE6tfukfv3AgrOApI3b9ao\npCQdevDB3GW+b76p6p07K7ZvXw2tX1+N/f0r5Q/i1Z71yiuv6P3339czzzyj8PBwy3JcobJmlQVl\n4OHK60UbWaevZp56otBtnqoxR5+c/ZfDbUTFx2tD//6FlvdauVLr588vlGM1sipOVmUck7uzyoJT\nS2FXlayqdpd7eXkXuV6Gg/3R9i9fB8BTUAawK9PnkoPlmUWu5+vgHRAXjwY8G2UAu2Jie+tZn8R8\ny2b6zFdMbFSR68XfdZdClyzJtyz0n/9UXL9+Lr+PAFyHYwYervzPJlqvKllVlOmTqZjYKD2ZEF/E\nFq5I3rxZC1avVrquzAji+vVTdM+eDnOsRFbFyaqMY3J3VllQBh6uMr5oK+OYyKo4OZU5qyzYTQQA\noAwAAFyOokJw56US3JVVGcdEVsXJcWdWYGCgW3LKijLwcO7c18i+YbLKM6syjqkiYTcRAIAyAABQ\nBgAAUQYAAFEGAABRBgAAUQYAAFEGcMLKlSsVFhaW75+3t7fWr1/v0pyjR4+qWbNmSk1NlSSlpqaq\nWbNm+vHHH12akyM1NVVDhgxRs2bN1Lp1a0VHR+v77793eU7Pnj21YcOGfMvmzZunkSNHujzL29tb\nYWFhuummmxQdHa09e/a4PCOHl5eXxo0bl/v17NmzNX36dEtyHnroodyvs7KyFBwcrDvvvNPlWVcT\nygCldvfddyslJSX334gRI9S9e3dFRRV9eevSCgkJ0YgRIzRhwgRJ0oQJE/TYY4+pUaNGLs3JMXTo\nUF177bX64osvtHfvXk2dOlXHjx93ec7AgQO1dOnSfMuWLVumQYMGuTyrWrVqSklJ0X/+8x89/PDD\nevrpp12ekaNq1apauXKlTp06Jcm6T/hWr15de/fuVXp6uiRp48aNatiwoVs/vVwZUQYokwMHDujp\np5/WO++8Y8n2R48erc8//1zz5s3T9u3b873zdKXz589r586deu655xQcHCxJCg8PV48ePVyedc89\n9yg5OVlZWVmSpCNHjuj48ePq2rWry7NyGGN08uRJ+flZ92eGqlSpouHDh2vu3LmWZeTo27evkpOT\nJUlJSUkaOHAgnyguI8oATsvMzNSgQYP04osvqmHDhpZk+Pj4aNasWRozZozmzZsnb++i/+yms9au\nXatu3bpZsu2CgoKC1KlTJ61du1aStHTpUt1///2WZKWlpSksLExNmzZVQkKCnn32WUtycowcOVJL\nlizR2bNnLc25//77tXTpUmVkZGj37t3q3LmzpXlXA8oATps6daratm2rAQMGWJrz4YcfqkGDBtq9\ne7dlGe7exZB3V9GyZcs0cOBAS3L8/f2VkpKiI0eO6OWXX9a9995rSU6OGjVqaPDgwUpMTCz+xmXQ\ntm1bHTlyRElJSYqOjrY062pBGcApW7du1cqVK7Vw4UJLc7755ht99NFH2rFjh+bOnatffvnFkpw+\nffpo27ZtlmzbnpiYGG3atEkpKSm6ePGiwsLCLM/s37+/9u3bp4sXL1qa8/jjj+uNN97QhQsXLM2J\niYnRuHHj2EXkIpQBSi3nrJu3335b1atXtyzHGKMRI0Zo/vz5CgkJ0fjx4y07ZhAQEKB27dppypQp\nOnHihCTpq6++0ieffGJZ3q233qohQ4ZYcuDYns8++0zNmzdXtWrVLM0JDAzUfffdpzfeeMPSGdcj\njzyihIQEtW7d2rKMqwllgFL7+9//rhMnTuivf/1rvtNLly9f7tKc119/XU2aNNFtt90m6cr+6H37\n9ln2Dn7RokX66aef1KlTJ7Vp00YzZszQddddZ0mWdGVX0e7duy3bRST9cczgpptu0qxZs/Tiiy9a\nlpX3F//YsWN18uRJS3Ouu+46xcbG5i7jbKKy4W8gIxfXrSerPLMq45gqEmYGAADKAABAGQAARBkA\nAEQZAABEGQAARBkAAEQZAAAk+ZT3HYBncdenON35aVGyKk6Wu3ICAwPdklORUAbIxScygasXu4kA\nAJQBAIAyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACI\nMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgy\nAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIA\nAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAA\niDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACI\nMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgyAACIMgAAiDIAAIgy\nAACIMgAAiDIAAIgyAACIMgAASPp/AVkqmw1ike4AAAAASUVORK5CYII=\n", "text": [ "